package BackTracking;

import java.util.Arrays;

/**
 * n皇后问题
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/27 16:47
 */
public class NQueens {

    public static void main(String[] args) {
        backtrack(1);
    }

    static int n = 4;
    static int[] item = new int[n + 1];
    static int num = 0;

    /**
     * 满m叉树
     * 约束条件：不同列、不同斜线
     * 限界条件：无
     * @param t
     */
    static void backtrack(int t) {
        if (t > n) {
            num++;
            for (int i = 1; i <= n; i++) {
                System.out.print(item[i] + "  ");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= n; i++) {
                if (abs(i, t)) {
                    item[t] = i;
                    backtrack(t + 1);
                }
            }
        }

    }

    private static boolean abs(int i, int t) {
        for (int j = 1; j < t; j++)
            if (item[j] == i || (Math.abs(t - j) == Math.abs(i - item[j])))
                return false;
        return true;
    }
}


